# 手动实现双链表
class Node():
    def __init__(self,data):
        self.data = data
        self.next = None
        self.prev = None
class MyLinkedList1():
    def __init__(self,ele=None):
        self.head = Node(None) # 虚拟头节点
        self.tail = Node(None) # 虚拟尾节点
        if ele == None:
            self.head.next = self.tail
            self.tail.prev = self.head
            self.size = 0
        else:
            eleNode = Node(ele)
            self.head.next = eleNode
            eleNode.prev = self.head
            eleNode.next = self.tail
            self.tail.prev = eleNode
            self.size = 1

    ## 增删改查
    ## 增
    def add_first(self,data):
        e = Node(data)
        temp=self.head.next
        e.next = temp
        temp.prev = e

        self.head.next = e
        e.prev = self.head
        self.size += 1
    def add_tail(self,data):
        e = Node(data)
        temp = self.tail.prev
        temp.next = e
        e.prev = temp
        e.next = self.tail
        self.tail.prev = e
        self.size += 1
    def add_index(self,index,e):
        self._check_position_index(index) # 判断链表是否越界
        e = Node(e)
        p = self.head
        for _ in range(index):
            p = p.next
        temp = p.next
        p.next = e
        e.prev = p
        e.next = temp
        temp.prev = e
        self.size += 1
    #删除
    def remove_first(self):
        if self.size < 1:
            raise IndexError("List is empty")
        x = self.head.next
        temp = x.next
        self.head.next = temp
        temp.prev =  self.head
        self.size -= 1
        return x.data
    def remove_lase(self):
        if self.size < 1:
            raise IndexError("List is empty")
        x = self.tail.prev
        temp = x.prev
        temp.next = self.tail
        self.tail.prev = temp
        self.size -= 1
        return x.data
    def remove_index(self,index):
        self._check_element_index(index)
        p = self.head
        for _ in range(index):
            p = p.next
        x = p.next
        temp = x.next
        temp.prev = p
        p.next = temp
        self.size -= 1
        return x.data
    # 改
    def set(self,index,e):
        self._check_element_index(index)
        p = self.head
        for _ in range(index+1):
            p = p.next
        p.data = e
    # 查
    def get(self,index,e):
        self._check_element_index(index)
        p = self.head
        for _ in range(index+1):
            p = p.next
        return p.data

    ## 常用操作
    # 1.链表长度
    def __len__(self):
        return self.size
    # 2.判断边界
    def _is_element_index(self,index):
        return 0 <= index < self.size
    def _is_position_index(self,index):
        return 0 <= index <= self.size
    def _check_element_index(self,index):
        if not self._is_element_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")
    def _check_position_index(self,index):
        if not self._is_position_index(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")
    # 3.打印整个链表
    def display(self):
        print(f"size={self.size}")
        p = self.head.next
        while p is not self.tail:
            print(f"{p.data} <->", end=" ")
            p = p.next
        print("null\n")
    # 4.判断链表是否为空
    def isEmpty(self):
        return self.size == 0
